package de.hsfulda.et.problemloesen.ws1112.grp2.knapsack;

import java.util.ArrayList;

public class DepthFirstSearch01 implements Optimizer {
    
    // extracted values
    private long weightMax;
    private long[] itemsWeightArray; 
    long counter = 0L;
    
    private long[] resultItemsWeigth;

    public Knapsack optimize(ArrayList<KnapsackItem> items,
	    ArrayList<Long> boundaryArrayList) 
    {
	this.counter = 0L;
	this.resultItemsWeigth = new long[items.size()];
	this.weightMax = boundaryArrayList.get(0);
	long zuladung = weightMax;
	this.itemsWeightArray = new long[items.size()];
	// prepare array with item weights
	for (int j = 0; j < itemsWeightArray.length; j++) {
	    itemsWeightArray[j] = items.get(j).getWeight().longValue();
	}
	
	optimizeRecursive(0, zuladung);
	
	Knapsack solution = new Knapsack(resultItemsWeigth.length);
	// pack knapsack object
	for (int j = 0; j < resultItemsWeigth.length; j++) {
	    if (resultItemsWeigth[j] != 0) // if it is in
		solution.packIn(new KnapsackItem(resultItemsWeigth[j]), j) ;
	}
	
	System.out.println("Couter: " + counter);
	return solution;
    }
    
    private boolean optimizeRecursive (int i, long zuladung)
    {
	boolean toReturn = false;
	counter++;
	
	if (zuladung == 0) 
	    toReturn = true;
	else if (i != itemsWeightArray.length -1)
	{
	    zuladung = (zuladung - itemsWeightArray[i]);
	    if (optimizeRecursive(i + 1, zuladung))
	    {
		resultItemsWeigth[i] = itemsWeightArray[i];
		toReturn = true;
	    }
	    else 
	    {
		zuladung = (zuladung + itemsWeightArray[i]);
		if (optimizeRecursive(i + 1, zuladung ))
		{
		    toReturn = true;
		}
	    }
	}
	else 
	{
	    if (zuladung == itemsWeightArray[i])
	    {
		resultItemsWeigth[i] = itemsWeightArray[i];
		toReturn = true;
	    }
	}
	return toReturn;
    }

}
